package simple;

import data.TreeNode;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/6/10 22:30
 */
public class No111_二叉树的最小深度 {
    public static void main(String[] args) {
        Solution111 solution111 = new Solution111();
        
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);

        root.right.left = new TreeNode(15);
        root.right.right= new TreeNode(7);

        int minDeep = solution111.minDepth(root);
        System.out.println(minDeep);
    }
}

class Solution111 {
    public int minDepth(TreeNode root) {
        //从根节点开始
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        } else if (root.left == null) {
            return minDepth(root.right, 2);
        } else if (root.right == null) {
            return minDepth(root.left, 2);
        } else {
            return Math.min(minDepth(root.left, 2), minDepth(root.right, 2));
        }
    }

    //以一个节点获取最小深度
    public int minDepth(TreeNode root,int deep) {
        if (root.left == null && root.right == null) {
            return deep;
        } else if (root.left == null) {
            return minDepth(root.right, ++deep);
        } else if (root.right == null) {
            return minDepth(root.left, ++deep);
        } else {
            ++deep;
            return Math.min(minDepth(root.left, deep), minDepth(root.right, deep));
        }
    }
}
